package com.xk._02算法篇._05backTracking.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/n-queens/
 * @description: 51 N皇后问题
 * @author: xu
 * @date: 2022/10/18 14:30
 */
public class Test01 {
    public static void main(String[] args) {
        List<List<String>> lists = new Test01().solveNQueens(4);
        System.out.println(lists);
    }

    public List<List<String>> solveNQueens(int n) {
        if (n < 1) return null;
        List<List<String>> res = new ArrayList<>();
        int[] queens = new int[n]; // 索引下标为行号，元素值为列号
        plate(0, res, queens);
        return res;
    }

    private void plate(int row, List<List<String>> res, int[] queens){
        if (row == queens.length) {
            put(res, queens);
            return;
        }

        for (int col = 0; col < queens.length; col++) {
            if (isValid(row, col, queens)){
                queens[row] = col;
                plate(row+1, res, queens);
            }
        }
    }

    private boolean isValid(int row, int col, int[] queens) {
        for (int i = 0; i < row; i++) {
            if (queens[i] == col) return false;
            if ((row - i) == Math.abs(col - queens[i])) return false;
        }
        return true;
    }

    private void put(List<List<String>> res, int[] queens) {
        List<String> list = new ArrayList<>();
        for (int r = 0; r < queens.length; r++){
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < queens.length; c++){
                if (queens[r] == c) sb.append("Q");
                else sb.append(".");
            }
            list.add(sb.toString());
        }
        res.add(list);
    }
}
